"""
题目:https://leetcode-cn.com/problems/longest-palindromic-substring/
    给你一个字符串 s，找到 s 中最长的回文子串.

    示例 1：
    输入：s = "babad"
    输出："bab"
    解释："aba" 同样是符合题意的答案。
思路：使用动态规划方法，核心思想是：如果一个字符串是回文字符串，那么去掉第一个字符和最后一个字符的子串仍然是回文字符串。


时间复杂度：O(n^2)
空间复杂度：O(n^2)
"""

class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        if size <= 1:
            return s

        dp = [[False] * size for _ in range(size)]
        max_len = 1
        start = 0
        for j in range(size):
            for i in range(j):
                #如果子串长度小于2：当子串长度为1时，那么它一定是回文字符串；如果子串长度为2，则需判断两个字符是否相等，相等则为回文字符串，否则不是回文字符串。
                if j - i <= 2:
                    if s[i] == s[j]:
                        dp[i][j] = True
                        cur_len = j - i + 1
                else:#如果子串长度大于2，那么当去掉首字符和尾字符后的子串是回文字符串且首字符和尾字符相等时，该子串才是回文字符串
                    if dp[i+1][j-1] and s[i] == s[j]:
                        dp[i][j] = True
                        cur_len = j - i + 1

                if dp[i][j]:#如果该子串是回文字符串，且当前子串的长度大于目前保存的最长子串长度，那么更新子串长度以及子串起始位置。
                    if cur_len > max_len:
                        max_len = cur_len
                        start = i
        return s[start:start+max_len]